// 2025/3/3
// https://leetcode.cn/problems/minimum-window-substring/?envType=study-plan-v2&envId=top-100-liked
// 最小覆盖子串

class Solution {
    public:
        string minWindow(string s, string t) {
            int m = s.size(), n = t.size();
            unordered_map<char, int> s_map, t_map;
            for (int i = 0; i < n; i++)
            {
                ++t_map[t[i]];
            }
    
            int count = 0, left = 0, right = -1, aim = t_map.size();
            int minLen = 10e5 + 1, minLeft = -1, minRight = -1;
            while (right < m)
            {
                if (count < aim)
                {
                    right++;
                    if (t_map[s[right]] != 0 && ++s_map[s[right]] == t_map[s[right]])
                        count++;
                }
                else if (count == aim)
                {
                    while (count == aim)
                    {
                        if (t_map[s[left]] != 0 && s_map[s[left]]-- == t_map[s[left]])
                            count--;
                        left++;
                    }
                    if (right - left + 2 < minLen)
                    {
                        minLen = right - left + 2;
                        minLeft = left - 1;
                        minRight = right;
                    }
                }
            }
    
            if (minLeft == -1 || minRight == -1)
                return string();
            string ans(&s[minLeft], &s[minRight] + 1);
            return ans;
        }
    };